package advance.day05;

/**
 * 描述：
 * 给定一颗二叉树的头节点，返回最大搜索二叉树的大小
 *
 * @author hl
 * @version 1.0
 * @date 2020/11/10 11:08
 */
public class BiggestSubBSTInTree {

    public static class ReturnType {
        int bstSize;
        Node bstHead;
        int max;
        int min;

        public ReturnType(int bstSize, Node bstHead, int max, int min) {
            this.bstSize = bstSize;
            this.bstHead = bstHead;
            this.max = max;
            this.min = min;
        }
    }

    public static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(0, null, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        //获取左右子树的信息
        ReturnType leftInfo = process(head.left);
        ReturnType rightInfo = process(head.right);
        //加工信息
        int includeItSelf = 0;
        if (head.left == leftInfo.bstHead && head.right == rightInfo.bstHead
                && head.value > leftInfo.max && head.value < rightInfo.min) {
            includeItSelf = leftInfo.bstSize + 1 +rightInfo.bstSize;
        }
        int p1 = leftInfo.bstSize;
        int p2 = rightInfo.bstSize;
        int maxSize = Math.max(Math.max(p1, p2), includeItSelf);
        Node maxHead = p1 > p2 ? leftInfo.bstHead : rightInfo.bstHead;
        if (maxSize == includeItSelf) {
            maxHead = head;
        }
        //将加工后的信息返回给父亲
        return new ReturnType(maxSize, maxHead,
                Math.max(Math.max(leftInfo.max, rightInfo.max), head.value),
                        Math.min(Math.min(leftInfo.min, rightInfo.min), head.value));
    }
}
